
    <html lang="zh-cn">
    <head>
    <meta content="text/html; charset=utf-8" http-equiv="content-type" />
    <link href="css/default.css" rel="stylesheet">
    <link href="css/github.css" rel="stylesheet">
    </head>
    <body>
    <h1 id="_1">线性表</h1>
<h2 id="_2">一、逻辑结构和基本操作</h2>
<h3 id="1">1. 逻辑结构</h3>
<ul>
<li>具有相同数据类型的n个数据元素的有限序列，表长n，n=0为空表</li>
<li>表头：第一个元素</li>
<li>表尾：最后一个元素</li>
<li>除第一个元素外，每个元素有且仅有一个直接前驱</li>
<li>除最后一个元素外，每个元素有且仅有一个直接后继</li>
</ul>
<h3 id="2">2. 基本操作</h3>
<div class="codehilite"><pre><span></span><code><span class="n">initList</span><span class="p">(</span><span class="o">&amp;</span><span class="n">L</span><span class="p">);</span>
<span class="n">len</span><span class="p">(</span><span class="n">L</span><span class="p">);</span>
<span class="n">locateElem</span><span class="p">(</span><span class="n">L</span><span class="p">,</span><span class="w"> </span><span class="n">i</span><span class="p">);</span>
<span class="n">getElem</span><span class="p">(</span><span class="n">L</span><span class="p">,</span><span class="w"> </span><span class="n">i</span><span class="p">);</span>
<span class="n">listInsert</span><span class="p">(</span><span class="o">&amp;</span><span class="n">L</span><span class="p">,</span><span class="w"> </span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">e</span><span class="p">);</span>
<span class="n">listDelete</span><span class="p">(</span><span class="o">&amp;</span><span class="n">L</span><span class="p">,</span><span class="w"> </span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="o">&amp;</span><span class="n">e</span><span class="p">);</span>
<span class="n">printList</span><span class="p">(</span><span class="n">L</span><span class="p">);</span>
<span class="n">isEmptyList</span><span class="p">(</span><span class="n">L</span><span class="p">);</span>
<span class="n">destroyList</span><span class="p">(</span><span class="o">&amp;</span><span class="n">L</span><span class="p">);</span>
</code></pre></div>

<h2 id="_3">二、顺序存储结构</h2>
<h3 id="1_1">1. 定义：又称顺序表，使用一组地址连续的存储单元，依次存储线性表的数据元素，使逻辑上相邻的两个元素物理位置也相邻</h3>
<ul>
<li>存储空间的起始位置data[ ]</li>
<li>顺序表最大存储容量MaxSize</li>
<li>顺序表当前最大长度len
特点</li>
<li>随机访存，O(1)时间复杂度访问</li>
<li>存储密度高，每个结点只存储数据元素</li>
<li>无需花费空间建立数据之间的逻辑关系，由物理位置相邻特性决定</li>
<li>逻辑上物理上均相邻，插入删除操作需要移动大量元素</li>
</ul>
<h3 id="2_1">2. 基本操作</h3>
<p>（1）插入元素</p>
<div class="codehilite"><pre><span></span><code><span class="c1">//插入元素</span>
<span class="n">boolean</span><span class="w"> </span><span class="nf">listInsert</span><span class="p">(</span><span class="n">SqList</span><span class="w"> </span><span class="o">&amp;</span><span class="n">L</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">Elemtype</span><span class="w"> </span><span class="n">e</span><span class="p">){</span>
<span class="w">    </span><span class="k">if</span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="o">||</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="o">&gt;</span><span class="w"> </span><span class="n">L</span><span class="p">.</span><span class="n">len</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span>
<span class="w">        </span><span class="k">return</span><span class="w"> </span><span class="mi">-1</span><span class="p">;</span>
<span class="w">    </span><span class="k">if</span><span class="p">(</span><span class="n">L</span><span class="p">.</span><span class="n">len</span><span class="w"> </span><span class="o">&gt;=</span><span class="w"> </span><span class="n">MaxSize</span><span class="p">)</span>
<span class="w">        </span><span class="k">return</span><span class="w"> </span><span class="mi">-1</span><span class="p">;</span>
<span class="w">    </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">j</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">L</span><span class="p">.</span><span class="n">len</span><span class="p">;</span><span class="w"> </span><span class="n">j</span><span class="w"> </span><span class="o">&gt;</span><span class="w"> </span><span class="n">i</span><span class="p">;</span><span class="w"> </span><span class="n">j</span><span class="o">--</span><span class="p">)</span>
<span class="w">        </span><span class="n">L</span><span class="p">.</span><span class="n">data</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">L</span><span class="p">.</span><span class="n">data</span><span class="p">[</span><span class="n">j</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">];</span>
<span class="w">    </span><span class="n">L</span><span class="p">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">e</span><span class="p">;</span>
<span class="w">    </span><span class="n">L</span><span class="p">.</span><span class="n">len</span><span class="o">++</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>

<p>分析
- 最好情况
- 最坏情况
- 平均情况
（2）删除元素</p>
    </body>
    </html>
    